<?php
// This file is part of Preg question type - https://code.google.com/p/oasychev-moodle-plugins/
//
// Preg question type is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// Moodle is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with Moodle.  If not, see <http://www.gnu.org/licenses/>.

/**
 * Defines generic node classes, generated by parser. These nodes will be usually aggregated in engine-specific classes.
 * These classes are used primarily to store data, so their variable memebers are public.
 *
 * @package    qtype_preg
 * @copyright  2012 Oleg Sychev, Volgograd State Technical University
 * @author     Oleg Sychev <oasychev@gmail.com>
 * @license    http://www.gnu.org/copyleft/gpl.html GNU GPL v3 or later
 */

defined('MOODLE_INTERNAL') || die();

global $CFG;
require_once($CFG->dirroot . '/question/type/poasquestion/poasquestion_string.php');
require_once($CFG->dirroot . '/question/type/preg/preg_unicode.php');

/**
 * Representation of nodes and leafs as they were typed in the regex.
 */
class qtype_preg_userinscription {
    /** General case, contains the same string as typed by user. */
    const TYPE_GENERAL = 'userinscription_general';
    /** Flag that needs an additional description that must be stored in the lang file (unicode properties names etc). */
    const TYPE_CHARSET_FLAG = 'userinscription_charset_flag';

    /** String with the leaf itself. */
    public $data = '';
    /** Type of the user inscription. */
    public $type = null;

    public function __construct($data = '', $type = self::TYPE_GENERAL) {
        $this->data = $data;
        $this->type = $type;
    }
}

/**
 * Class for plain lexems (not complete nodes), they contain position information too.
 */
class qtype_preg_lexem {
    /** Subtype of the lexem. */
    public $subtype;
    /** Indexes of first and last characters of the lexem. */
    public $indfirst = -1;
    public $indlast = -1;
    /** An instance of qtype_preg_userinscription. */
    public $userinscription = null;

    public function __construct($subtype, $indfirst, $indlast, $userinscription) {
        $this->subtype = $subtype;
        $this->indfirst = $indfirst;
        $this->indlast = $indlast;
        $this->userinscription = $userinscription;
    }
}

/**
 * Class for plain subpattern lexems.
 */
class qtype_preg_lexem_subpatt extends qtype_preg_lexem {
    /** Number of the subpattern. */
    public $number;

    public function __construct($subtype, $indfirst, $indlast, $userinscription, $number) {
        parent::__construct($subtype, $indfirst, $indlast, $userinscription);
        $this->number = $number;
    }
}

/**
 * The interface for objects that are passed to qtype_preg_leaf::match(), qtype_preg_leaf::consumes(), qtype_preg_leaf::next_character() as $matcherstateobj.
 */
interface qtype_preg_matcher_state {

    /**
     * Returns index of the first character matched for the given subpattern.
     */
    public function index_first($subpattern = 0);

    /**
     * Returns the length of the given subpattern.
     */
    public function length($subpattern = 0);

    /**
     * Returns whether the given subpattern is captured.
     */
    public function is_subpattern_captured($subpattern);
}

/**
 * Generic node class.
 */
abstract class qtype_preg_node {

    /** Abstract node class, not representing real things. */
    const TYPE_ABSTRACT = 'node_abstract';
    /** A character or a character set. */
    const TYPE_LEAF_CHARSET = 'leaf_charset';
    /** Meta-character or escape sequence matching with a set of characters that couldn't be enumerated. */
    const TYPE_LEAF_META = 'leaf_meta';
    /** Simple assert: ^ $ or escape-sequence. */
    const TYPE_LEAF_ASSERT = 'leaf_assert';
    /** Back reference to subpattern. */
    const TYPE_LEAF_BACKREF = 'leaf_backref';
    /** Recursive match. */
    const TYPE_LEAF_RECURSION = 'leaf_recursion';
    /** Backtracking control, newline conventions etc sequences. */
    const TYPE_LEAF_CONTROL = 'leaf_control';
    /** Option set. */
    const TYPE_LEAF_OPTIONS = 'leaf_options';
    /** Finite quantifier. */
    const TYPE_NODE_FINITE_QUANT = 'node_finite_quant';
    /** Infinite quantifier. */
    const TYPE_NODE_INFINITE_QUANT = 'node_infinite_quant';
    /** Concatenation. */
    const TYPE_NODE_CONCAT = 'node_concat';
    /** Alternative. */
    const TYPE_NODE_ALT = 'node_alt';
    /** Assert with expression within. */
    const TYPE_NODE_ASSERT = 'node_assert';
    /** Subpattern. */
    const TYPE_NODE_SUBPATT = 'node_subpatt';
    /** Conditional subpattern. */
    const TYPE_NODE_COND_SUBPATT = 'node_cond_subpatt';
    /** Error node. */
    const TYPE_NODE_ERROR = 'node_error';

    /** Type one the node - should be equal to a constant defined in this class. */
    public $type;
    /** Subtype, defined by a child class. */
    public $subtype;
    /** Error data for the subtype. */
    public $error = null;
    /** Indexes of first and last characters of the node in the regex. */
    public $indfirst = -1;
    public $indlast = -1;
    /** An instance of qtype_preg_userinscription. */
    public $userinscription = null;
    /** Identifier of this node. */
    public $id = -1;

    public function __construct() {
        $this->type = self::TYPE_ABSTRACT;
    }

    /**
     * Sets indexes and userinscription for the node.
     */
    public function set_user_info($indfirst, $indlast, $userinscription = null) {
        $this->indfirst = $indfirst;
        $this->indlast = $indlast;
        $this->userinscription = $userinscription;
    }

    /**
     * Return class name without 'qtype_preg_' prefix. Interface string for the node name should be exactly
     * the same (and start from an upper-case character) if class not overloading ui_nodename method.
     */
    public function name() {
        return $this->type;
    }

    /**
     * Returns the dot script corresponding to this node.
     * @param styleprovider an object prividing styles for different node types.
     * @param isroot if true, adds the "digraph {\n" to the start and "}" to the end.
     * @return mixed the dot script if this is the root, array(dot script, node styles) otherwise.
     */
    abstract public function dot_script($styleprovider, $isroot = true);


    /**
     * May be overloaded by childs to change name using data from $this->pregnode.
     */
    public function ui_nodename() {
        return get_string($this->name(), 'qtype_preg');
    }
}

/**
 * Generic leaf class.
 */
abstract class qtype_preg_leaf extends qtype_preg_node {

    /** Is matching case insensitive? */
    public $caseinsensitive = false;
    /** Is this leaf negative? */
    public $negative = false;
    /** Assertions merged into this node (qtype_preg_leaf_assert objects). */
    public $mergedassertions = array();

    public function __clone() {
        // When clonning a leaf we also want the merged assertions to be cloned
        foreach ($this->mergedassertions as $i => $mergedassertion) {
            $this->mergedassertions[$i] = clone $mergedassertion;
        }
    }

    public function dot_script($styleprovider, $isroot = true) {
        // Calculate the node name, style and the result.
        $nodename = $this->id;
        $style = $nodename . $styleprovider->get_style($this) . ';';
        $dotscript = $nodename . ';';
        if ($isroot) {
            $dotscript = $styleprovider->get_dot_head() . $style . $dotscript . $styleprovider->get_dot_tail();
            return $dotscript;
        } else {
            return array($dotscript, $style);
        }
    }

    /**
     * Returns the number of characters consumed by this leaf: 0 in case of an assertion or eps-leaf,
     * 1 in case of a single character, n in case of a backreferense.
     * @param matcherstateobj an object which implements qtype_preg_matcher_state interface.
     * @return number of characters consumed by this leaf.
     */
    public function consumes($matcherstateobj = null) {
        return 1;
    }

    /**
     * Returns true if character(s) starting from $str[$pos] match(es) this leaf, false otherwise
     * Contains universal code to deal with merged assertions. Overload match_inner to define your leaf type matching
     * @param str the string being matched.
     * @param pos position of character in the string, if leaf is non-consuming than position before this character is analyzed.
     * @param length an integer variable to store the length of the match.
     * @param matcherstateobj an object which implements the qtype_preg_matcher_state interface.
     */
    public function match($str, $pos, &$length, $matcherstateobj = null) {
        $result = true;
        // Check merged assertions first.
        foreach($this->mergedassertions as $assert) {
            $result = $result && $assert->match($str, $pos, $length, $matcherstateobj);
        }
        // Now check this leaf.
        $result = $result && $this->match_inner($str, $pos, $length, $matcherstateobj);
        return $result;
    }

    /**
     * Returns true if character(s) starting from $str[$pos] matches with leaf, false otherwise
     * Implements details of a particular leaf matching.
     * @param str the string being matched.
     * @param pos position of character in the string, if leaf is non-consuming than position before this character is analyzed.
     * @param length an integer variable to store the length of the match.
     * @param matcherstateobj an object which implements the qtype_preg_matcher_state interface.
     */
    abstract protected function match_inner($str, $pos, &$length, $matcherstateobj = null);

    /**
     * Returns a character suitable for both this leaf and merged assertions and the previous character.
     * @param str string already matched.
     * @param pos position of the last matched character in the string.
     * @param length number of characters matched (can be greater than 0 in case of a partial backreference match).
     * @param matcherstateobj an object which implements the qtype_preg_matcher_state interface.
     */
    abstract public function next_character($str, $pos, $length = 0, $matcherstateobj = null);

    /**
     * Returns a human-readable form of this leaf.
     * @return human-readable string describing this leaf.
     */
    abstract public function tohr();
}

/**
 * Represents a character or a charcter set.
 */
class qtype_preg_leaf_charset extends qtype_preg_leaf {

    /** Simple flags in the disjunctive normal form. */
    public $flags = null;   // array(array());
    /** A range is a pair of integers, ranges are 3-dimensional array of integers or 2-dimensional array of pairs. */
    protected $ranges = array();
    /** Array of assertion flags (it's impossible to calculate an assertion as a range), each asserts[i] is an array of 0/1/2 asserts as flags; for ranges[i]. */
    protected $asserts = array();
    /** true if the charset is a DNF range matrix, false if charset is DNF of flags. */
    public $israngecalculated = true;

    public function __construct() {
        $this->type = qtype_preg_node::TYPE_LEAF_CHARSET;
    }

    public function __clone() {
        parent::__clone();
        if ($this->flags !== null) {
            foreach ($this->flags as $ind1 => $extflag) {
                $cur = array();
                foreach ($extflag as $ind2 => $inflag) {
                    $cur[$ind2] = clone $inflag;
                }
                $this->flags[$ind1] = $cur;
            }
        }
    }

    protected function calc_ranges() {
        $this->israngecalculated = true;
        die('implement range calulate before use it!');
    }

    protected function match_inner($str, $pos, &$length, $matcherstateobj = null) {
        if ($pos < 0 || $pos >= $str->length()) {
            return false;
        }
        $result = false;
        if ($this->flags === null) {
            return false;
        }

        foreach ($this->flags as $flags) {
            // Get intersection of all current flags.
            $result = !empty($flags);
            foreach ($flags as $flag) {
                $result = $result && $flag->match($str, $pos, !$this->caseinsensitive);
                if (!$result) {
                    break;
                }
            }
            $result = ($result xor $this->negative);
            if ($result) {
                $length = 1;
                return true;
            }
        }

        $length = 0;
        return false;
    }

    public function next_character($str, $pos, $length = 0, $matcherstateobj = null) { // TODO may be rename to character?
        foreach ($this->flags as $flags) {
            // Get intersection of all current flags.
            $ranges = array(array(0, qtype_preg_unicode::max_possible_code()));
            foreach ($flags as $flag) {
                if ($flag->type === qtype_preg_charset_flag::SET) {
                    $currange = qtype_preg_unicode::get_ranges_from_charset($flag->data);
                } else {
                    $currange = call_user_func('qtype_preg_unicode::' . $flag->data . '_ranges');
                }
                if ($flag->negative) {
                    $currange = qtype_preg_unicode::negate_ranges($currange);
                }
                $ranges = qtype_preg_unicode::intersect_ranges($ranges, $currange);
            }
            if ($this->negative) {
                $ranges = qtype_preg_unicode::negate_ranges($ranges);
            }
            // Check all the returned ranges.
            foreach ($ranges as $range) {
                for ($i = $range[0]; $i <= $range[1]; $i++) {
                    $c = new qtype_poasquestion_string(qtype_poasquestion_string::code2utf8($i));
                    //if ($this->match($c, 0, $l)) {
                    return $c;
                    //}
                }
            }
        }
        return new qtype_poasquestion_string('');
    }

    /**
     * Check if other charset is included in this. That means that any character matching other also matches this.
     * @param other charset to check.
     * @return true if included, false otherwise
     */
    public function is_include(qtype_preg_leaf_charset $other) {
        /*$result = true;
        for ($i = 32; $result && $i < 126; $i++) {
            $c = new qtype_poasquestion_string(chr($i));
            $result = $result && (!$this->match($c, 0, $l) && $other->match($c, 0, $l));
        }
        return $result || $other===$this;*/
        //getting ranges of this charset
        foreach ($this->flags as $flags) {
            foreach ($flags as $flag) {
                // Get intersection of all current flags.
                $range = array(array('negative' => false, 0 => 0, 1 => qtype_preg_unicode::max_possible_code()));
                if ($flag->type === qtype_preg_charset_flag::SET) {
                    $currange = qtype_preg_unicode::get_ranges_from_charset($flag->data);
                } else {
                    $currange = call_user_func('qtype_preg_unicode::' . $flag->data . '_ranges');
                }
                foreach ($currange as &$tmp) {
                    $tmp['negative'] = $flag->negative;
                }
                $ranges = qtype_preg_unicode::intersect_ranges($range, $currange);
                if ($this->negative) {
                    foreach ($ranges as &$tmp)
                        $tmp['negative'] = true;
                    $ranges = qtype_preg_unicode::intersect_ranges($ranges, array('negative' => false, 0 => 0, 1 => qtype_preg_unicode::max_possible_code()));
                }
            }
        }
        //getting ranges of other charset
        foreach ($other->flags as $flags) {
            foreach ($flags as $flag) {
                // Get intersection of all current flags.
                $range = array(array('negative' => false, 0 => 0, 1 => qtype_preg_unicode::max_possible_code()));
                if ($flag->type === qtype_preg_charset_flag::SET) {
                    $currange = qtype_preg_unicode::get_ranges_from_charset($flag->data);
                } else {
                    $currange = call_user_func('qtype_preg_unicode::' . $flag->data . '_ranges');
                }
                foreach ($currange as &$tmp) {
                    $tmp['negative'] = $flag->negative;
                }
                $otherranges = qtype_preg_unicode::intersect_ranges($range, $currange);
                if ($other->negative) {
                    foreach ($otherranges as &$tmp)
                        $tmp['negative'] = true;
                    $otherranges = qtype_preg_unicode::intersect_ranges($otherranges, array('negative' => false, 0 => 0, 1 => qtype_preg_unicode::max_possible_code()));
                }
            }
        }
        //comparing ranges of this and other charsets
        if (is_array($ranges)) {
              $included = true;
        } else {
            return false;
        }
        /*foreach($ranges as $i=>$ran) {
               $ranges[$i] = array ('negative'=>false, 0=>$ranges[$i][0], 1=>$ranges[$i][1]);
        }
        foreach($otherranges as $i=>$ran) {
               $otherranges[$i] = array ('negative'=>false, 0=>$otherranges[$i][0], 1=>$otherranges[$i][1]);
        }
        $ranges = qtype_preg_unicode::intersect_ranges(array($ranges, $otherranges));*/
        for (reset($ranges), reset($otherranges); $included && current($ranges)!==false; next($ranges), next($otherranges)) {
               if (current($ranges)!=current($otherranges)) {
                    $included = false;
                    /*while (next($ranges)!==false && current($ranges)!=current($otherranges)) {
                         next($ranges);
                    }
                    if (current($ranges)!==false) {
                    $included = true;
                    }*/
               }
        }
        return $included;
    }
    public function is_part_ident(qtype_preg_leaf_charset $other) {
        /*$flag1 = false;
        $flag2 = false;
        for ($i = 32; !($flag1 && $flag2) && $i < 126; $i++) {
            $c=chr($i);
            $flag1 = $flag1 || ($this->match($c, 0, $l) && $other->match($c, 0, $l));
            $flag2 = $flag2 || (!$this->match($c, 0, $l) && $other->match($c, 0, $l) || $this->match($c, 0, $l) && !$other->match($c, 0, $l));
        }
        return $flag1 && $flag2;*/
        foreach ($this->flags as $flags) {
            foreach ($flags as $flag) {
                // Get intersection of all current flags.
                $range = array(array('negative' => false, 0 => 0, 1 => qtype_preg_unicode::max_possible_code()));
                if ($flag->type === qtype_preg_charset_flag::SET) {
                    $currange = qtype_preg_unicode::get_ranges_from_charset($flag->data);
                } else {
                    $currange = call_user_func('qtype_preg_unicode::' . $flag->data . '_ranges');
                }
                foreach ($currange as &$tmp) {
                    $tmp['negative'] = $flag->negative;
                }
                $ranges = qtype_preg_unicode::intersect_ranges($range, $currange);
                if ($this->negative) {
                    foreach ($ranges as &$tmp)
                        $tmp['negative'] = true;
                    $ranges = qtype_preg_unicode::intersect_ranges($ranges, array('negative' => false, 0 => 0, 1 => qtype_preg_unicode::max_possible_code()));
                }
            }
        }
        //getting ranges of other charset
        foreach ($other->flags as $flags) {
            foreach ($flags as $flag) {
                // Get intersection of all current flags.
                $range = array(array('negative' => false, 0 => 0, 1 => qtype_preg_unicode::max_possible_code()));
                if ($flag->type === qtype_preg_charset_flag::SET) {
                    $currange = qtype_preg_unicode::get_ranges_from_charset($flag->data);
                } else {
                    $currange = call_user_func('qtype_preg_unicode::' . $flag->data . '_ranges');
                }
                foreach ($currange as &$tmp) {
                    $tmp['negative'] = $flag->negative;
                }
                $otherranges = qtype_preg_unicode::intersect_ranges($range, $currange);
                if ($other->negative) {
                    foreach ($otherranges as &$tmp)
                        $tmp['negative'] = true;
                    $otherranges = qtype_preg_unicode::intersect_ranges($otherranges, array('negative' => false, 0 => 0, 1 => qtype_preg_unicode::max_possible_code()));
                }
            }
        }
        //comparing ranges of this and other charsets
        if (is_array($ranges)) {
              $included = false;
        } else {
            return false;
        }
        /*foreach($ranges as $i=>$ran) {
               $ranges[$i] = array ('negative'=>false, 0=>$ranges[$i][0], 1=>$ranges[$i][1]);
        }
        foreach($otherranges as $i=>$ran) {
               $otherranges[$i] = array ('negative'=>false, 0=>$otherranges[$i][0], 1=>$otherranges[$i][1]);
        }
        $ranges = qtype_preg_unicode::intersect_ranges(array($ranges, $otherranges));*/
        for (reset($ranges), reset($otherranges); $included && current($ranges)!==false; next($ranges), next($otherranges)) {
               if (current($ranges)==current($otherranges)) {
                    $included = true;
                    /*while (next($ranges)!==false && current($ranges)!=current($otherranges)) {
                         next($ranges);
                    }
                    if (current($ranges)!==false) {
                    $included = true;
                    }*/
               }
        }
        return $included;
    }

    public function tohr() {
        $result = '';
        foreach ($this->flags as $ind1 => $extflag) {
            $cur = '';
            foreach ($extflag as $ind2 => $inflag) {
                $cur .= $inflag->tohr();
                if ($ind2 != count($extflag) - 1) {
                    $cur .= '&&';
                }
            }
            $result .= $cur;
            if ($ind1 != count($this->flags) - 1) {
                $result .= ' || ';
            }
        }
        return $result;
    }

    public function add_flag_dis(qtype_preg_charset_flag $flag) {
        echo 'implement add_flag before use!';
    }

    public function add_flag_con(qtype_preg_charset_flag $flag) {
        echo 'implement add_flag before use!';
    }

    /**
     * Intersects this charset with other one.
     * @param other charset to intersect with.
     * @return an object of qtype_preg_leaf_charset which is the intersection of this and other.
     */
    public function intersect(qtype_preg_leaf_charset $other) {
        if ($this->negative) {
            $this->push_negative();
        }
        if ($other->negative) {
            $other->push_negative();
        }
        foreach ($this->flags as $disjunct1) {
            foreach ($other->flags as $disjunct2) {
                $resflags[] = array_merge($disjunct1, $disjunct2);
            }
        }
        $result = new qtype_preg_leaf_charset;
        $result->flags = $resflags;
        $result->israngecalculated = false;
        return $result;
    }

    /**
     * Substracts other charset from this.
     * @param other charset to substract.
     * @return an object of qtype_preg_leaf_charset which is the substraction of this and other.
     */
    public function substract(qtype_preg_leaf_charset $other) {
        $other->negative = !$other->negative;
        $result = $this->intersect($other);
        $other->negative = !$other->negative;
        return $result;
    }
}

/**
 * Represents a part of a charset - can be a numerable characters, flag like \w, \d or a unicode property.
 */
class qtype_preg_charset_flag {

    // Charset types.
    const SET                    = 'enumerable_characters';
    const FLAG                   = 'functionally_calculated_characters';
    const UPROP                  = 'unicode_property';
    const CIRCUMFLEX             = 'circumflex';
    const DOLLAR                 = 'dollar';

    // Flag types.
    const DIGIT                  = 'digit';      // \d AND [:digit:]
    const XDIGIT                 = 'xdigit';     // [:xdigit:]
    const SPACE                  = 'space';      // \s AND [:space:]
    const WORD                   = 'word';       // \w AND [:word:]
    const ALNUM                  = 'alnum';      // [:alnum:]
    const ALPHA                  = 'alpha';      // [:alpha:]
    const ASCII                  = 'ascii';      // [:ascii:]
    const CNTRL                  = 'cntrl';      // [:ctrl:]
    const GRAPH                  = 'graph';      // [:graph:]
    const LOWER                  = 'lower';      // [:lower:]
    const UPPER                  = 'upper';      // [:upper:]
    const PRIN                   = 'print';      // [:print:] PRIN, because PRINT is php keyword
    const PUNCT                  = 'punct';      // [:punct:]
    const HSPACE                 = 'hspace';     // \h
    const VSPACE                 = 'vspace';     // \v
    const UPROPCC                = 'Cc';         // Control
    const UPROPCF                = 'Cf';         // Format
    const UPROPCN                = 'Cn';         // Unassigned
    const UPROPCO                = 'Co';         // Private use
    const UPROPCS                = 'Cs';         // Surrogate
    const UPROPC                 = 'C';          // Other
    const UPROPLL                = 'Ll';         // Lower case letter
    const UPROPLM                = 'Lm';         // Modifier letter
    const UPROPLO                = 'Lo';         // Other letter
    const UPROPLT                = 'Lt';         // Title case letter
    const UPROPLU                = 'Lu';         // Upper case letter
    const UPROPL                 = 'L';          // Letter
    const UPROPMC                = 'Mc';         // Spacing mark
    const UPROPME                = 'Me';         // Enclosing mark
    const UPROPMN                = 'Mn';         // Non-spacing mark
    const UPROPM                 = 'M';          // Mark
    const UPROPND                = 'Nd';         // Decimal number
    const UPROPNL                = 'Nl';         // Letter number
    const UPROPNO                = 'No';         // Other number
    const UPROPN                 = 'N';          // Number
    const UPROPPC                = 'Pc';         // Connector punctuation
    const UPROPPD                = 'Pd';         // Dash punctuation
    const UPROPPE                = 'Pe';         // Close punctuation
    const UPROPPF                = 'Pf';         // Final punctuation
    const UPROPPI                = 'Pi';         // Initial punctuation
    const UPROPPO                = 'Po';         // Other punctuation
    const UPROPPS                = 'Ps';         // Open punctuation
    const UPROPP                 = 'P';          // Punctuation
    const UPROPSC                = 'Sc';         // Currency symbol
    const UPROPSK                = 'Sk';         // Modifier symbol
    const UPROPSM                = 'Sm';         // Mathematical symbol
    const UPROPSO                = 'So';         // Other symbol
    const UPROPS                 = 'S';          // Symbol
    const UPROPZL                = 'Zl';         // Line separator
    const UPROPZP                = 'Zp';         // Paragraph separator
    const UPROPZS                = 'Zs';         // Space separator
    const UPROPZ                 = 'Z';          // Separator
    const UPROPXAN               = 'Xan';        // Any alphanumeric character
    const UPROPXPS               = 'Xps';        // Any POSIX space character
    const UPROPXSP               = 'Xsp';        // Any Perl space character
    const UPROPXWD               = 'Xwd';        // Any Perl "word" character
    const ARABIC                 = 'Arabic';
    const ARMENIAN               = 'Armenian';
    const AVESTAN                = 'Avestan';
    const BALINESE               = 'Balinese';
    const BAMUM                  = 'Bamum';
    const BENGALI                = 'Bengali';
    const BOPOMOFO               = 'Bopomofo';
    const BRAILLE                = 'Braille';
    const BUGINESE               = 'Buginese';
    const BUHID                  = 'Buhid';
    const CANADIAN_ABORIGINAL    = 'Canadian_Aboriginal';
    const CARIAN                 = 'Carian';
    const CHAM                   = 'Cham';
    const CHEROKEE               = 'Cherokee';
    const COMMON                 = 'Common';
    const COPTIC                 = 'Coptic';
    const CUNEIFORM              = 'Cuneiform';
    const CYPRIOT                = 'Cypriot';
    const CYRILLIC               = 'Cyrillic';
    const DESERET                = 'Deseret';
    const DEVANAGARI             = 'Devanagari';
    const EGYPTIAN_HIEROGLYPHS   = 'Egyptian_Hieroglyphs';
    const ETHIOPIC               = 'Ethiopic';
    const GEORGIAN               = 'Georgian';
    const GLAGOLITIC             = 'Glagolitic';
    const GOTHIC                 = 'Gothic';
    const GREEK                  = 'Greek';
    const GUJARATI               = 'Gujarati';
    const GURMUKHI               = 'Gurmukhi';
    const HAN                    = 'Han';
    const HANGUL                 = 'Hangul';
    const HANUNOO                = 'Hanunoo';
    const HEBREW                 = 'Hebrew';
    const HIRAGANA               = 'Hiragana';
    const IMPERIAL_ARAMAIC       = 'Imperial_Aramaic';
    const INHERITED              = 'Inherited';
    const INSCRIPTIONAL_PAHLAVI  = 'Inscriptional_Pahlavi';
    const INSCRIPTIONAL_PARTHIAN = 'Inscriptional_Parthian';
    const JAVANESE               = 'Javanese';
    const KAITHI                 = 'Kaithi';
    const KANNADA                = 'Kannada';
    const KATAKANA               = 'Katakana';
    const KAYAH_LI               = 'Kayah_Li';
    const KHAROSHTHI             = 'Kharoshthi';
    const KHMER                  = 'Khmer';
    const LAO                    = 'Lao';
    const LATIN                  = 'Latin';
    const LEPCHA                 = 'Lepcha';
    const LIMBU                  = 'Limbu';
    const LINEAR_B               = 'Linear_B';
    const LISU                   = 'Lisu';
    const LYCIAN                 = 'Lycian';
    const LYDIAN                 = 'Lydian';
    const MALAYALAM              = 'Malayalam';
    const MEETEI_MAYEK           = 'Meetei_Mayek';
    const MONGOLIAN              = 'Mongolian';
    const MYANMAR                = 'Myanmar';
    const NEW_TAI_LUE            = 'New_Tai_Lue';
    const NKO                    = 'Nko';
    const OGHAM                  = 'Ogham';
    const OLD_ITALIC             = 'Old_Italic';
    const OLD_PERSIAN            = 'Old_Persian';
    const OLD_SOUTH_ARABIAN      = 'Old_South_Arabian';
    const OLD_TURKIC             = 'Old_Turkic';
    const OL_CHIKI               = 'Ol_Chiki';
    const ORIYA                  = 'Oriya';
    const OSMANYA                = 'Osmanya';
    const PHAGS_PA               = 'Phags_Pa';
    const PHOENICIAN             = 'Phoenician';
    const REJANG                 = 'Rejang';
    const RUNIC                  = 'Runic';
    const SAMARITAN              = 'Samaritan';
    const SAURASHTRA             = 'Saurashtra';
    const SHAVIAN                = 'Shavian';
    const SINHALA                = 'Sinhala';
    const SUNDANESE              = 'Sundanese';
    const SYLOTI_NAGRI           = 'Syloti_Nagri';
    const SYRIAC                 = 'Syriac';
    const TAGALOG                = 'Tagalog';
    const TAGBANWA               = 'Tagbanwa';
    const TAI_LE                 = 'Tai_Le';
    const TAI_THAM               = 'Tai_Tham';
    const TAI_VIET               = 'Tai_Viet';
    const TAMIL                  = 'Tamil';
    const TELUGU                 = 'Telugu';
    const THAANA                 = 'Thaana';
    const THAI                   = 'Thai';
    const TIBETAN                = 'Tibetan';
    const TIFINAGH               = 'Tifinagh';
    const UGARITIC               = 'Ugaritic';
    const VAI                    = 'Vai';
    const YI                     = 'Yi';

    /** Is this flag negative? */
    public $negative = false;
    /** Type of this flag, can be either TYPE_SET or TYPE_FLAG or TYPE_UPROP or TYPE_CIRCUMFLEX or TYPE_DOLLAR. */
    public $type;
    /** Characters, flag or unicode property if this is a TYPE_SET, TYPE_FLAG or TYPE_UPROP correspondingly. */
    public $data;

    public function __clone() {
        if (is_object($this->data)) {
            $this->data = clone $this->data;
        }
    }

    /**
     * Sets the subtype and the data of this flag.
     * @param type a constant defining the subtype of this flag.
     * @param data the concrete value of this flag - characters, a flag or a unicode property.
     */
    public function set_data($type, $data) {
        $this->type = $type;
        $this->data = $data;
    }

    public function is_null_length() {
        return $this->type === self::CIRCUMFLEX || $this->type === self::DOLLAR;
    }

    public function match($str, $pos, $cs) {
        if ($pos < 0 || $pos >= $str->length()) {
            return false;    // String index out of borders.
        }

        $char = $str[$pos];
        if (!$cs) {
            $charlower = qtype_poasquestion_string::strtolower($char);
            $charupper = qtype_poasquestion_string::strtoupper($char);
        }

        switch ($this->type) {
            case self::CIRCUMFLEX:
                return (($pos === 0) xor $this->negative);
            case self::DOLLAR:
                return (($pos === $str->length() - 1) xor $this->negative);
            case self::SET:
                $ranges = qtype_preg_unicode::get_ranges_from_charset($this->data);
                break;
            case self::FLAG:
            case self::UPROP:
                $ranges = call_user_func('qtype_preg_unicode::' . $this->data . '_ranges');
                break;
        }

        if ($cs) {
            $result = qtype_preg_unicode::is_in_range($char, $ranges);
        } else {
            $result = qtype_preg_unicode::is_in_range($charlower, $ranges) || qtype_preg_unicode::is_in_range($charupper, $ranges);
        }
        return ($result xor $this->negative);
    }

    public function tohr() {
        $result = '';
        switch ($this->type) {
        case self::CIRCUMFLEX:
            $result = '^';
            break;
        case self::DOLLAR:
            $result = '$';
            break;
        case self::SET:
            $result = $this->data;
            break;
        case self::FLAG:
            $result = $this->data;
            break;
        case self::UPROP:
            $result = 'todo';
            break;
        default:
            return '';
        }
        if ($this->negative) {
            $result = '!' . $result;
        }
        return $result;
    }
}

/**
 * Defines meta-characters that can't be enumerated.
 */
class qtype_preg_leaf_meta extends qtype_preg_leaf {

    //Leaf with empty in alternative (something|)
    const SUBTYPE_EMPTY = 'empty_leaf_meta';
    //Service subtype - end of regex, but not end of string
    const SUBTYPE_ENDREG = 'endreg_leaf_meta';

    public function __construct($subtype = null) {
        $this->type = qtype_preg_node::TYPE_LEAF_META;
        $this->subtype = $subtype;
    }

    //TODO - ui_nodename()

    public function consumes($matcherstateobj = null) {
        return 0;
    }

    public function next_character($str, $pos, $length = 0, $matcherstateobj = null) {
        return new qtype_poasquestion_string('');
    }

    protected function match_inner($str, $pos, &$length, $matcherstateobj = null) {
        $length = 0;
        return true;
    }

    public function tohr() {
        switch ($this->subtype) {
            case qtype_preg_leaf_meta::SUBTYPE_ENDREG:
                return 'metaENDREG';
            case qtype_preg_leaf_meta::SUBTYPE_EMPTY:
                return 'metaEPS';
            default:
                return '';
        }
    }
}

/**
 * Defines simple assertions.
 */
class qtype_preg_leaf_assert extends qtype_preg_leaf {

    /** ^ */
    const SUBTYPE_CIRCUMFLEX = 'circumflex_leaf_assert';
    /** $ */
    const SUBTYPE_DOLLAR = 'dollar_leaf_assert';
    /** \b */
    const SUBTYPE_ESC_B = 'esc_b_leaf_assert';
    /** \A */
    const SUBTYPE_ESC_A = 'esc_a_leaf_assert';
    /** \z */
    const SUBTYPE_ESC_Z = 'esc_z_leaf_assert';
    /** \G */
    const SUBTYPE_ESC_G = 'esc_g_leaf_assert';

    public function __construct($subtype = null, $negative = false) {
        $this->type = qtype_preg_node::TYPE_LEAF_ASSERT;
        $this->subtype = $subtype;
        $this->negative = $negative;
    }

    public function consumes($matcherstateobj = null) {
        return 0;
    }

    //TODO - ui_nodename()
    protected function match_inner($str, $pos, &$length, $matcherstateobj = null) {
        $length = 0;
        switch ($this->subtype) {
            case qtype_preg_leaf_assert::SUBTYPE_ESC_A:    // Because there can be only one line is the response.
            case qtype_preg_leaf_assert::SUBTYPE_ESC_G:    // There are no repetitive matching for now, so \G is equvivalent to \A.
            case qtype_preg_leaf_assert::SUBTYPE_CIRCUMFLEX:
                $result = ($pos === 0);
                break;
            case qtype_preg_leaf_assert::SUBTYPE_ESC_Z:    // Because there can be only one line is the response.
            case qtype_preg_leaf_assert::SUBTYPE_DOLLAR:
                $result = ($pos === $str->length());
                break;
            case qtype_preg_leaf_assert::SUBTYPE_ESC_B:
                $alnumrange = qtype_preg_unicode::alnum_ranges();
                $start = $pos === 0 && ($str[0] === '_' || qtype_preg_unicode::is_in_range($str[0], $alnumrange));
                $end = $pos === $str->length() && ($str[$pos - 1] === '_' || qtype_preg_unicode::is_in_range($str[$pos - 1], $alnumrange));
                $wW = $Ww = false;
                if ($pos > 0 && $pos < $str->length()) {
                    $wW = ($str[$pos - 1] === '_' || qtype_preg_unicode::is_in_range($str[$pos - 1], $alnumrange)) && !($str[$pos] === '_' || qtype_preg_unicode::is_in_range($str[$pos], $alnumrange));
                    $Ww = !($str[$pos - 1] === '_' || qtype_preg_unicode::is_in_range($str[$pos - 1], $alnumrange)) && ($str[$pos] === '_' || qtype_preg_unicode::is_in_range($str[$pos], $alnumrange));
                }
                $result = ($start || $end || $wW || $Ww);
                break;
            default:
                $result = false;
        }
        if ($this->negative) {
            $result = !$result;
        }
        return $result;
    }
    public function next_character($str, $pos, $length = 0, $matcherstateobj = null) {
        switch ($this->subtype) {
            case qtype_preg_leaf_assert::SUBTYPE_ESC_A:    // Because there can be only one line is the response.
            case qtype_preg_leaf_assert::SUBTYPE_ESC_G:
            case qtype_preg_leaf_assert::SUBTYPE_CIRCUMFLEX:
                if ($this->negative) {
                    return 'notstringstart';
                } else {
                    return 'stringstart';
                }
                break;
            case qtype_preg_leaf_assert::SUBTYPE_ESC_Z:    // Because there can be only one line is the response.
            case qtype_preg_leaf_assert::SUBTYPE_DOLLAR:
                if ($this->negative) {
                    return ' notstringend';
                } else {
                    return '';
                }
                break;
            case qtype_preg_leaf_assert::SUBTYPE_ESC_B:
                if ($this->negative) {
                    return 'notwordchar';
                } else {
                    return 'wordchar';
                }
                break;
        }
    }
    public function tohr() {
        switch ($this->subtype) {
            case qtype_preg_leaf_assert::SUBTYPE_ESC_A:    // Because there can be only one line is the response.
            case qtype_preg_leaf_assert::SUBTYPE_ESC_G:
            case qtype_preg_leaf_assert::SUBTYPE_CIRCUMFLEX:
                $type = '^';
                break;
            case qtype_preg_leaf_assert::SUBTYPE_ESC_Z:    // Because there can be only one line is the response.
            case qtype_preg_leaf_assert::SUBTYPE_DOLLAR:
                $type = '$';
                break;
            case qtype_preg_leaf_assert::SUBTYPE_ESC_B:
                $type = '\\b';
                break;
        }
        if ($this->negative) {
            return '!assert' . $type;
        } else {
            return 'assert' . $type;
        }
    }
}

/**
 * Defines backreferences.
 */
class qtype_preg_leaf_backref extends qtype_preg_leaf {
    /** The number of a subpattern to refer to. */
    public $number;

    public function __construct($number = null) {
        $this->type = qtype_preg_node::TYPE_LEAF_BACKREF;
        $this->number = $number;
    }

    public function consumes($matcherstateobj = null) {
        if (!$matcherstateobj->is_subpattern_captured($this->number)) {
            return qtype_preg_matching_results::UNKNOWN_CHARACTERS_LEFT;
        }
        return $matcherstateobj->length($this->number);
    }

    protected function match_inner($str, $pos, &$length, $matcherstateobj = null) {
        $length = 0;
        $subpattlen = $matcherstateobj->length($this->number);
        $start = $matcherstateobj->index_first($this->number);
        $end = $start + $subpattlen - 1;

        if (!$matcherstateobj->is_subpattern_captured($this->number) || ($subpattlen > 0 && $pos >= $str->length())) {
            return false;
        } else if ($subpattlen === 0) {
            return true;
        }

        $strcopy = clone $str;
        if ($this->caseinsensitive) {
            $strcopy->tolower();
        }
        $matchlen = 0;
        $result = true;
        // Check char by char.
        for ($i = $start; $result && $i <= $end && $matchlen + $pos < $str->length(); $i++) {
            $result = $result && ($strcopy[$i] === $strcopy[$pos + $matchlen]);
            if ($result) {
                $matchlen++;
            }
        }
        // If the string has not enough characters.
        if ($pos + $subpattlen - 1 >= $str->length()) {
            $result = false;
        }
        $length = $matchlen;
        return $result;
    }

    public function next_character($str, $pos, $length = 0, $matcherstateobj = null) {
        // TODO: check for assertions in case of $length == 0
        if (!$matcherstateobj->is_subpattern_captured($this->number)) {
            return new qtype_poasquestion_string('');
        }
        $start = $matcherstateobj->index_first($this->number);
        $end = $start + $matcherstateobj->length($this->number);
        if ($end > $str->length()) {
            return new qtype_poasquestion_string('');
        }
        return $str->substring($start + $length, $end - $start - $length);
    }

    public function tohr() {
        return 'backref #' . $this->number;
    }
}

class qtype_preg_leaf_option extends qtype_preg_leaf {
    public $posopt;
    public $negopt;

    public function __construct($posopt = null, $negopt = null) {
        $this->type = qtype_preg_node::TYPE_LEAF_OPTIONS;
        $this->posopt = $posopt;
        $this->negopt = $negopt;
    }
    protected function match_inner($str, $pos, &$length, $matcherstateobj = null) {
        die ('TODO: implements abstract function match for qtype_preg_leaf_option class before use it!');
    }
    public function next_character($str, $pos, $length = 0, $matcherstateobj = null) {
        die ('TODO: implements abstract function character for qtype_preg_leaf_option class before use it!');
    }
    public function tohr() {
        $result = '(?';
        if (!empty($this->posopt)) {
            $result .= $this->posopt;
        }
        if (!empty($this->negopt)) {
            $result .= '-'.$this->negopt;
        }
        return $result.')';
    }
}

class qtype_preg_leaf_recursion extends qtype_preg_leaf {

    public $number;

    public function __construct($number = null) {
        $this->type = qtype_preg_node::TYPE_LEAF_RECURSION;
        $this->number = $number;
    }
    protected function match_inner($str, $pos, &$length, $matcherstateobj = null) {
        die ('TODO: implements abstract function match for qtype_preg_leaf_recursion class before use it!');
    }
    public function next_character($str, $pos, $length = 0, $matcherstateobj = null) {
        die ('TODO: implements abstract function character for qtype_preg_leaf_recursion class before use it!');
    }
    public function tohr() {
        return 'recursion';
    }
}

/**
 * Reperesents backtracking control, newline convention etc sequences like (*...).
 */
class qtype_preg_leaf_control extends qtype_preg_leaf {

    /** (*ACCEPT) */
    const SUBTYPE_ACCEPT = 'accept_leaf_control';
    /** (*FAIL) */
    const SUBTYPE_FAIL = 'fail_leaf_control';
    /** (*MARK:NAME) */
    const SUBTYPE_MARK_NAME = 'mark_name_leaf_control';

    /** (*COMMIT) */
    const SUBTYPE_COMMIT = 'commit_leaf_control';
    /** (*PRUNE) */
    const SUBTYPE_PRUNE = 'prune_leaf_control';
    /** (*SKIP) */
    const SUBTYPE_SKIP = 'skip_leaf_control';
    /** (*SKIP:NAME) */
    const SUBTYPE_SKIP_NAME = 'skip_name_leaf_control';
    /** (*THEN) */
    const SUBTYPE_THEN = 'then_leaf_control';

    /** (*CR) */
    const SUBTYPE_CR = 'cr_leaf_control';
    /** (*LF) */
    const SUBTYPE_LF = 'lf_leaf_control';
    /** (*CRLF) */
    const SUBTYPE_CRLF = 'crlf_leaf_control';
    /** (*ANYCRLF) */
    const SUBTYPE_ANYCRLF = 'anycrlf_leaf_control';
    /** (*ANY) */
    const SUBTYPE_ANY = 'any_leaf_control';

    /** (*BSR_ANYCRLF) */
    const SUBTYPE_BSR_ANYCRLF = 'bsr_anycrlf_leaf_control';
    /** (*BSR_UNICODE) */
    const SUBTYPE_BSR_UNICODE = 'bsr_unicode_leaf_control';

    /** (*NO_START_OPT) */
    const SUBTYPE_NO_START_OPT = 'no_start_opt_leaf_control';
    /** (*UTF8) */
    const SUBTYPE_UTF8 = 'utf8_leaf_control';
    /** (*UTF16) */
    const SUBTYPE_UTF16 = 'utf16_leaf_control';
    /** (*UCP) */
    const SUBTYPE_UCP = 'ucp_leaf_control';

    public $name;

    public function __construct($subtype = null, $name = null) {
        $this->type = qtype_preg_node::TYPE_LEAF_CONTROL;
        $this->subtype = $subtype;
        $this->name = $name;
    }
    protected function match_inner($str, $pos, &$length, $matcherstateobj = null) {
        // Do nothing, the matching should be controlled by the matching engine.
    }
    public function next_character($str, $pos, $length = 0, $matcherstateobj = null) {
        // Do nothing, the matching should be controlled by the matching engine.
    }
    public function tohr() {
        return 'control';
    }
}


/**
 * Defines operator nodes.
 */
abstract class qtype_preg_operator extends qtype_preg_node {

    /** An array of operands. */
    public $operands = array();

    public function __clone() {
        // When clonning an operator we also want its subtree to be cloned.
        foreach ($this->operands as $i => $operand) {
            $this->operands[$i] = clone $operand;
        }
    }

    public function dot_script($styleprovider, $isroot = true) {
        // Calculate the node name and style.
        $nodename = $this->id;
        $style = $nodename . $styleprovider->get_style($this) . ';';

        // Get child dot scripts and styles.
        $childscripts = array();
        foreach ($this->operands as $operand) {
            $tmp = $operand->dot_script($styleprovider, false);
            $childscripts[] = $tmp[0];
            $style .= $tmp[1];
        }

        // Form the result.
        $dotscript = '';
        foreach ($childscripts as $childscript) {
            $dotscript .= $nodename . '->' . $childscript;
        }
        if ($isroot) {
            $dotscript = $styleprovider->get_dot_head() . $style . $dotscript . $styleprovider->get_dot_tail();
            return $dotscript;
        } else {
            return array($dotscript, $style);
        }
        return $result;
    }
}


/**
 * Defines finite quantifiers with left and right borders, unary operator.
 * Possible errors: left border is greater than right one.
 */
class qtype_preg_node_finite_quant extends qtype_preg_operator {

    /** Is quantifier lazy? */
    public $lazy;
    /** Is quantifier greed? */
    public $greed;
    /** Is quantifier possessive? */
    public $possessive;
    /** Smallest possible repetition number. */
    public $leftborder;
    /** Biggest possible repetition number. */
    public $rightborder;

    public function __construct($leftborder = 0, $rightborder = 0, $lazy = false, $greed = true, $possessive = false) {
        $this->type = qtype_preg_node::TYPE_NODE_FINITE_QUANT;
        $this->leftborder = $leftborder;
        $this->rightborder = $rightborder;
        $this->lazy = $lazy;
        $this->greed = $greed;
        $this->possessive = $possessive;
    }
    //TODO - ui_nodename()
}

/**
 * Defines infinite quantifiers node with the left border only, unary operator.
 */
class qtype_preg_node_infinite_quant extends qtype_preg_operator {

    /** Is quantifier lazy? */
    public $lazy;
    /** Is quantifier greed? */
    public $greed;
    /** Is quantifier possessive? */
    public $possessive;
    /** Smallest possible repetition number. */
    public $leftborder;

    public function __construct($leftborder = 0, $lazy = false, $greed = true, $possessive = false) {
        $this->type = qtype_preg_node::TYPE_NODE_INFINITE_QUANT;
        $this->leftborder = $leftborder;
        $this->lazy = $lazy;
        $this->greed = $greed;
        $this->possessive = $possessive;
    }
    //TODO - ui_nodename()
}

/**
 * Defines concatenation, binary operator.
 */
class qtype_preg_node_concat extends qtype_preg_operator {

    public function __construct() {
        $this->type = qtype_preg_node::TYPE_NODE_CONCAT;
    }
}

/**
 * Defines alternative, binary operator.
 */
class qtype_preg_node_alt extends qtype_preg_operator {

    public function __construct() {
        $this->type = qtype_preg_node::TYPE_NODE_ALT;
    }
}

/**
 * Defines lookaround assertions, unary operator.
 */
class qtype_preg_node_assert extends qtype_preg_operator {

    /** Positive lookahead assert. */
    const SUBTYPE_PLA = 'pla_node_assert';
    /** Negative lookahead assert. */
    const SUBTYPE_NLA = 'nla_node_assert';
    /** Positive lookbehind assert. */
    const SUBTYPE_PLB = 'plb_node_assert';
    /** Negative lookbehind assert. */
    const SUBTYPE_NLB = 'nlb_node_assert';

    public function __construct($subtype = null) {
        $this->type = qtype_preg_node::TYPE_NODE_ASSERT;
        $this->subtype = $subtype;
    }

    public function tohr() {
        return 'node assert';
    }

    //TODO - ui_nodename()
}

/**
 * Defines subpatterns, unary operator.
 */
class qtype_preg_node_subpatt extends qtype_preg_operator {

    /** Subpattern. */
    const SUBTYPE_SUBPATT = 'subpatt_node_subpatt';
    /** Once-only subpattern. */
    const SUBTYPE_ONCEONLY = 'onceonly_node_subpatt';
    /** Grouping node. For author's tools only.*/
    const SUBTYPE_GROUPING = 'grouping_node_supbatt';
    /** Duplicate subpatterns. For author's tools only.*/
    const SUBTYPE_DUPLICATE_SUBPATTERNS = 'duplicate_node_subpatt';

    /** Subpattern number. */
    public $number = -1;
    /** Array of numbers of nested subpatterns. */
    public $nested = array();

    public function __construct($number = -1, $nested = array()) {
        $this->type = qtype_preg_node::TYPE_NODE_SUBPATT;
        $this->number = $number;
        $this->nested = $nested;
    }

    //TODO - ui_nodename()
}

/**
 * Defines conditional subpatterns, unary, binary or ternary operator.
 * The first operand yes-pattern, second - no-pattern, third - the lookaround assertion (if any).
 * Possible errors: there is no backreference with such number in expression
 */
class qtype_preg_node_cond_subpatt extends qtype_preg_operator {

    /** Absolute/relative/named references to subpatterns. */
    const SUBTYPE_SUBPATT = 'subpatt_node_cond_subpatt';
    /** Recursion condition. */
    const SUBTYPE_RECURSION = 'recursion_node_cond_subpatt';
    /** Define subpattern for reference. */
    const SUBTYPE_DEFINE = 'define_node_cond_subpatt';
    /** Positive lookahead assert. */
    const SUBTYPE_PLA = 'pla_node_cond_subpatt';
    /** Negative lookahead assert. */
    const SUBTYPE_NLA = 'nla_node_cond_subpatt';
    /** Positive lookbehind assert. */
    const SUBTYPE_PLB = 'plb_node_cond_subpatt';
    /** Negative lookbehind assert. */
    const SUBTYPE_NLB = 'nlb_node_cond_subpatt';

    /** Subpattern number. */
    public $number = -1;
    /** Is condition satisfied?. */
    public $condbranch = null;

    public function __construct($subtype = null, $number = -1, $condbranch = null) {
        $this->type = qtype_preg_node::TYPE_NODE_COND_SUBPATT;
        $this->subtype = $subtype;
        $this->number = $number;
        $this->condbranch = $condbranch;
    }

    //TODO - ui_nodename()
}

/**
 * Defines error nodes, used when syntax errors in the regular expression occur.
 */
class qtype_preg_node_error extends qtype_preg_operator {

    const SUBTYPE_UNKNOWN_ERROR                = 'unknown_error_node_error';                    // Unknown parse error.
    const SUBTYPE_CONDSUBPATT_TOO_MUCH_ALTER   = 'consubpatt_too_much_alter_node_error';        // Too much top-level alternatives in a conditional subpattern.
    const SUBTYPE_WRONG_CLOSE_PAREN            = 'wrong_close_paren_node_error';                // Closing paren without opening  xxx).
    const SUBTYPE_WRONG_OPEN_PAREN             = 'wrong_open_paren_node_error';                 // Opening paren without closing  (xxx.
    const SUBTYPE_QUANTIFIER_WITHOUT_PARAMETER = 'quantifier_without_parameter_node_error';     // Quantifier at the start of the expression  - NOTE - currently incompatible with PCRE which treat it as a character.
    const SUBTYPE_UNCLOSED_CHARSET             = 'unclosed_charset_node_error';                 // Unclosed brackets in a character set.
    const SUBTYPE_SET_UNSET_MODIFIER           = 'set_and_unset_same_modifier_node_error';      // Set and unset same modifier at ther same time.
    const SUBTYPE_UNKNOWN_UNICODE_PROPERTY     = 'unknown_unicode_property_node_error';         // Unknown unicode property.
    const SUBTYPE_UNKNOWN_POSIX_CLASS          = 'unknown_posix_class_node_error';              // Unknown posix class.
    const SUBTYPE_UNKNOWN_CONTROL_SEQUENCE     = 'unknown_control_sequence_node_error';         // Unknown control sequence (*...).
    const SUBTYPE_INCORRECT_CHARSET_RANGE      = 'incorrect_charset_range_node_error';          // Incorrect character set range: [z-a].
    const SUBTYPE_INCORRECT_QUANT_RANGE        = 'incorrect_quant_range_node_error';            // Incorrect quantifier ranges: {5,3}.
    const SUBTYPE_SLASH_AT_END_OF_PATTERN      = 'slash_at_end_of_pattern_node_error';          // \ at end of pattern.
    const SUBTYPE_C_AT_END_OF_PATTERN          = 'c_at_end_of_pattern_node_error';              // \c at end of pattern.
    const SUBTYPE_INVALID_ESCAPE_SEQUENCE      = 'invalid_escape_sequence_node_error';          // Invalid escape sequence.
    const SUBTYPE_POSIX_CLASS_OUTSIDE_CHARSET  = 'posix_class_outside_charset_node_error';      // POSIX class ouside of a character set.
    const SUBTYPE_UNEXISTING_SUBPATT           = 'unexisting_subpatt_node_error';               // Reference to unexisting subpattern.
    const SUBTYPE_UNKNOWN_MODIFIER             = 'unknown_modifier_node_error';                 // Unknown, wrong or unsupported modifier.
    const SUBTYPE_MISSING_COMMENT_ENDING       = 'missing_comment_ending_node_error';           // Missing ) after comment.
    const SUBTYPE_MISSING_CONDSUBPATT_ENDING   = 'missing_condsubpatt_ending_node_error';       // Missing conditional subpattern name ending.
    const SUBTYPE_MISSING_CALLOUT_ENDING       = 'missing_callout_ending_node_error';           // Missing ) after (?C.
    const SUBTYPE_MISSING_SUBPATT_ENDING       = 'missing_subpatt_name_ending_node_error';      // Missing subpattern name ending.
    const SUBTYPE_MISSING_BACKREF_ENDING       = 'missing_backref_name_ending_node_error';      // Missing backreference name ending.
    const SUBTYPE_MISSING_BACKREF_BEGINNING    = 'missing_backref_name_beginning_node_error';   // Missing backreference name beginning.
    const SUBTYPE_MISSING_CONTROL_ENDING       = 'missing_control_ending_node_error';           // Missing ) after control sequence.
    const SUBTYPE_WRONG_CONDSUBPATT_NUMBER     = 'wrong_condsubpatt_number_node_error';         // Wrong conditional subpattern number, digits expected.
    const SUBTYPE_CONDSUBPATT_ASSERT_EXPECTED  = 'condsubpatt_assert_expected_node_error';      // Assertion or condition expected.
    const SUBTYPE_CHAR_CODE_TOO_BIG            = 'char_code_too_big_node_error';                // Character code too big.
    const SUBTYPE_CHAR_CODE_DISALLOWED         = 'char_code_disallowed_node_error';             // Character code disallowed.
    const SUBTYPE_CONSUBPATT_ZERO_CONDITION    = 'condsubpatt_zero_condition_node_error';       // Invalid condition (?(0).
    const SUBTYPE_CALLOUT_BIG_NUMBER           = 'callout_big_number_node_error';               // Too big number in (?C...).
    const SUBTYPE_DUPLICATE_SUBPATT_NAMES      = 'duplicate_subpatt_names_node_error';          // Two named subpatterns have the same name.
    const SUBTYPE_BACKREF_TO_ZERO              = 'backref_to_zero_error';                       // Backreference to the whole expression.
    const SUBTYPE_DIFFERENT_SUBPATT_NAMES      = 'different_subpatt_names_node_error';          // Different subpattern names for subpatterns of the same number.
    const SUBTYPE_SUBPATT_NAME_EXPECTED        = 'subpatt_name_expected_node_error';            // Subpattern name expected.
    const SUBTYPE_CX_SHOULD_BE_ASCII           = 'cx_should_be_ascii_node_error';               // \c should be followed by an ascii character.
    const SUBTYPE_LNU_UNSUPPORTED              = 'lnu_unsupported_node_error';                  // \L, \l, \N{name}, \U, and \u are unsupported.
    const SUBTYPE_UNRECOGNIZED_LBA             = 'unrecognized_lab_node_error';                 // Unrecognized character after (?<.

    /** Error strings names in qtype_preg.php lang file. */
    public static $errstrs = array(self::SUBTYPE_UNKNOWN_ERROR                => 'error_PCREincorrectregex',
                                   self::SUBTYPE_CONDSUBPATT_TOO_MUCH_ALTER   => 'error_threealtincondsubpatt',
                                   self::SUBTYPE_WRONG_CLOSE_PAREN            => 'error_unopenedparen',
                                   self::SUBTYPE_WRONG_OPEN_PAREN             => 'error_unclosedparen',
                                   self::SUBTYPE_QUANTIFIER_WITHOUT_PARAMETER => 'error_quantifieratstart',
                                   self::SUBTYPE_UNCLOSED_CHARSET             => 'error_unclosedsqbrackets',
                                   self::SUBTYPE_SET_UNSET_MODIFIER           => 'error_setunsetmod',
                                   self::SUBTYPE_UNKNOWN_UNICODE_PROPERTY     => 'error_unknownunicodeproperty',
                                   self::SUBTYPE_UNKNOWN_POSIX_CLASS          => 'error_unknownposixclass',
                                   self::SUBTYPE_UNKNOWN_CONTROL_SEQUENCE     => 'error_unknowncontrolsequence',
                                   self::SUBTYPE_INCORRECT_CHARSET_RANGE      => 'error_incorrectcharsetrange',
                                   self::SUBTYPE_INCORRECT_QUANT_RANGE        => 'error_incorrectquantrange',
                                   self::SUBTYPE_SLASH_AT_END_OF_PATTERN      => 'error_slashatendofpattern',
                                   self::SUBTYPE_C_AT_END_OF_PATTERN          => 'error_catendofpattern',
                                   self::SUBTYPE_INVALID_ESCAPE_SEQUENCE      => 'error_invalidescapesequence',
                                   self::SUBTYPE_POSIX_CLASS_OUTSIDE_CHARSET  => 'error_posixclassoutsidecharset',
                                   self::SUBTYPE_UNEXISTING_SUBPATT           => 'error_unexistingsubpatt',
                                   self::SUBTYPE_UNKNOWN_MODIFIER             => 'error_unknownmodifier',
                                   self::SUBTYPE_MISSING_COMMENT_ENDING       => 'error_missingcommentending',
                                   self::SUBTYPE_MISSING_CONDSUBPATT_ENDING   => 'error_missingcondsubpattending',
                                   self::SUBTYPE_MISSING_CALLOUT_ENDING       => 'error_missingcalloutending',
                                   self::SUBTYPE_MISSING_SUBPATT_ENDING       => 'error_missingsubpattending',
                                   self::SUBTYPE_MISSING_BACKREF_ENDING       => 'error_missingbackrefending',
                                   self::SUBTYPE_MISSING_BACKREF_BEGINNING    => 'error_missingbackrefbeginning',
                                   self::SUBTYPE_MISSING_CONTROL_ENDING       => 'error_missingcontrolending',
                                   self::SUBTYPE_WRONG_CONDSUBPATT_NUMBER     => 'error_wrongcondsubpattnumber',
                                   self::SUBTYPE_CONDSUBPATT_ASSERT_EXPECTED  => 'error_condsubpattassertexpected',
                                   self::SUBTYPE_CHAR_CODE_TOO_BIG            => 'error_charcodetoobig',
                                   self::SUBTYPE_CHAR_CODE_DISALLOWED         => 'error_charcodedisallowed',
                                   self::SUBTYPE_CONSUBPATT_ZERO_CONDITION    => 'error_condsubpattzerocondition',
                                   self::SUBTYPE_CALLOUT_BIG_NUMBER           => 'error_calloutbignumber',
                                   self::SUBTYPE_DUPLICATE_SUBPATT_NAMES      => 'error_duplicatesubpattnames',
                                   self::SUBTYPE_BACKREF_TO_ZERO              => 'error_backreftozero',
                                   self::SUBTYPE_DIFFERENT_SUBPATT_NAMES      => 'error_differentsubpattnames',
                                   self::SUBTYPE_SUBPATT_NAME_EXPECTED        => 'error_subpattnameexpected',
                                   self::SUBTYPE_CX_SHOULD_BE_ASCII           => 'error_cxshouldbeascii',
                                   self::SUBTYPE_LNU_UNSUPPORTED              => 'error_lnuunsupported',
                                   self::SUBTYPE_UNRECOGNIZED_LBA             => 'error_unrecognizedlba'
                                   );
    /** Additional info. */
    public $addinfo;

    public function __construct($subtype = null, $addinfo = null) {
        $this->type = qtype_preg_node::TYPE_NODE_ERROR;
        $this->subtype = $subtype;
        $this->addinfo = $addinfo;
    }

    public function dot_script($styleprovider, $isroot = true) {
        // Calculate the node name, style and the result.
        $nodename = $this->id;
        $style = $nodename . $styleprovider->get_style($this) . ';';
        $dotscript = $nodename . ';';
        if ($isroot) {
            $dotscript = $styleprovider->get_dot_head() . $style . $dotscript . $styleprovider->get_dot_tail();
            return $dotscript;
        } else {
            return array($dotscript, $style);
        }
    }

    /**
     * Returns a user interface error string for the error, represented by this node.
     */
    public function error_string() {
        $a = new stdClass;
        $a->indfirst = $this->indfirst;
        $a->indlast = $this->indlast;
        $a->addinfo = $this->addinfo;
        return get_string(qtype_preg_node_error::$errstrs[$this->subtype], 'qtype_preg', $a);
    }
}
